﻿using System;
using System.Collections.Generic;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;
using Algoritmia.Utils.Backtracers;
using Lists = Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.Knapsack
{
    public class KnapsackSolver : SpaceSavingKnapsackSolver3
    {
        private readonly Func<int, int, IMap<Tuple<int, int>, double>> _createMap;
        private readonly Func<int, int, IMap<Tuple<int, int>, Tuple<int, int>>> _createBackpointersMap;
        private readonly Func<IMap<Tuple<int, int>, Tuple<int, int>>, IBacktracer<Tuple<int, int>, int>> _createBacktracer;


        public KnapsackSolver(Func<int,int,IMap<Tuple<int,int>,double>> createMap = null,
                              Func<int,int,IMap<Tuple<int,int>,Tuple<int,int>>> createBackpointersMap = null,
                              Func<IMap<Tuple<int,int>,Tuple<int,int>>,IBacktracer<Tuple<int,int>,int>> createBacktracer = null)
        {
            _createMap = createMap ?? ((a, b) => AlgoritmiaFactory.Maps<Tuple<int, int>, double>.Default);
            _createBackpointersMap = createBackpointersMap ??
                                     ((a, b) => AlgoritmiaFactory.Maps<Tuple<int, int>, Tuple<int, int>>.Default);
            _createBacktracer = createBacktracer ?? (back => new DynamicBacktracer<Tuple<int, int>, int>(back));
        }

        public IEnumerable<int> Decisions(int W, Lists.IList<double> values, Lists.IList<int> weights)
        {
            var N = values.Count;
            var B = _createMap(N, W);
            var back = _createBackpointersMap(N, W);
            for (int c = 0; c <= W; c++)
            {
                var tp = new Tuple<int, int>(0, c);
                B[tp] = 0;
                back[tp] = tp;
            }
            for (int n = 1; n <= N; n++)
            {
                for (int c = 0; c < weights[n - 1]; c++)
                {
                    var tp = new Tuple<int, int>(n, c);
                    var tp2 = new Tuple<int, int>(n - 1, c);
                    B[tp] = B[tp2];
                    back[tp] = tp2;
                }
                for (int c = weights[n - 1]; c <= W; c++)
                {
                    var tp = new Tuple<int, int>(n, c);
                    var noGetCall = new Tuple<int, int>(n - 1, c);
                    var getCall = new Tuple<int, int>(n - 1, c - weights[n - 1]);
                    if ( B[noGetCall] > B[getCall] + values[n - 1])
                    {
                        B[tp] = B[noGetCall];
                        back[tp] = noGetCall;
                    }
                    else
                    {
                        B[tp] = B[getCall] + values[n - 1];
                        back[tp] = getCall;
                    }
                }
            }
            return _createBacktracer(back).Backtrace(new Tuple<int, int>(N, W), (tp, bp) => tp.Item2 > bp[tp].Item2 ? 1 : 0);
        }
    }
}
